package cn.st4rlight.util.lru;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;

import lombok.Getter;

/**
 * NOTE: 该类来源：Dubbo实现
 *
 * 一个LRU实现，需要的东西包括
 * 1. 一个CacheNode，记录前、后、key、value、所在链
 * 2. 一个CacheDeque，记录头尾的dummy node，以及链接的下一个deque。提供3个方法，一个addToLast，一个pollFirst，一个isEmpty判断
 * 3. 一个freqTable，记录每个频次的链表，以及频次对应的下一个频次的链表
 *
 * 目前该实现实际上是LFU + LRU，当频次超过一定阈值后就变为了LRU
 *
 * @param <K>
 * @param <V>
 */
public class LFUCache<K, V> {

    // 记录每个key对应的Node
    private final Map<K, CacheNode<K, V>> map;
    // 前n - 1个按照频率记录，最后一个按照LRU模式
    private final CacheDeque<K, V>[] freqTable;

    // 最大数量（同时也作为最大频次使用，当 >= 这个频次时，变为LFU）
    @Getter
    private final int capacity;

    @Getter
    private int currSize = 0;
    // 达到capacity后，每次需要移除的元素个数
    private final int evictionCount;

    private final ReentrantLock lock = new ReentrantLock();
    private static final int DEFAULT_INITIAL_CAPACITY = 1000;
    private static final float DEFAULT_EVICTION_FACTOR = 0.75f;

    public LFUCache() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_EVICTION_FACTOR);
    }

    /**
     * 初始化
     */
    @SuppressWarnings("unchecked")
    public LFUCache(final int maxCapacity, final float evictionFactor) {
        if (maxCapacity <= 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " + maxCapacity);
        }

        boolean factorInRange = evictionFactor <= 1 && evictionFactor > 0;
        if (!factorInRange || Float.isNaN(evictionFactor)) {
            throw new IllegalArgumentException("Illegal eviction factor value:" + evictionFactor);
        }

        // 总量和每次移除个数
        this.capacity = maxCapacity;
        this.evictionCount = (int) (capacity * evictionFactor);

        this.map = new HashMap<>();
        this.freqTable = new CacheDeque[capacity + 1];
        for (int i = 0; i <= capacity; i++) {
            freqTable[i] = new CacheDeque<>();
        }

        for (int i = 0; i < capacity; i++) {
            freqTable[i].nextDeque = freqTable[i + 1];
        }
        // 最后一个格子的下一个仍然指向最后一个
        freqTable[capacity].nextDeque = freqTable[capacity];
    }

    /**
     * 如果key存在，拿到这个node，重置其访问频次为0
     * 如果key不存在，说明要放入新的node，计算size，若超过个数则触发移除，然后写入到频次deque中
     */
    public V put(final K key, final V value) {
        CacheNode<K, V> node;
        lock.lock();
        try {
            node = map.get(key);
            if (node != null) {
                CacheNode.withdrawNode(node);
                node.value = value;
                freqTable[0].addLastNode(node);
                map.put(key, node);
            } else {
                currSize++;
                if (currSize > capacity) {
                    proceedEviction();
                }
                node = freqTable[0].addLast(key, value);
                map.put(key, node);
            }
        } finally {
            lock.unlock();
        }
        return node.value;
    }

    /**
     * 存在则移除
     */
    public V remove(final K key) {
        CacheNode<K, V> node = null;
        lock.lock();
        try {
            if (map.containsKey(key)) {
                node = map.remove(key);
                if (node != null) {
                    CacheNode.withdrawNode(node);
                }
                currSize--;
            }
        } finally {
            lock.unlock();
        }
        return (node != null) ? node.value : null;
    }

    /**
     * 存在则返回，同时移动所在频次
     */
    public V get(final K key) {
        CacheNode<K, V> node = null;
        lock.lock();
        try {
            if (map.containsKey(key)) {
                node = map.get(key);
                CacheNode.withdrawNode(node);
                node.owner.nextDeque.addLastNode(node);
            }
        } finally {
            lock.unlock();
        }
        return (node != null) ? node.value : null;
    }

    /**
     * 移除元素，直到剩余个数满足要求
     */
    private int proceedEviction() {
        int targetSize = capacity - evictionCount;
        int evictedElements = 0;

        FREQ_TABLE_ITER_LOOP:
        for (int i = 0; i <= capacity; i++) {
            CacheNode<K, V> node;
            while (!freqTable[i].isEmpty()) {
                node = freqTable[i].pollFirst();
                remove(node.key);
                if (targetSize >= currSize) {
                    break FREQ_TABLE_ITER_LOOP;
                }
                evictedElements++;
            }
        }
        return evictedElements;
    }

    /**
     * 节点实现，包含前指针、后指针、key、value，以及所属队列owner
     */
    private static class CacheNode<K, V> {

        CacheNode<K, V> prev;
        CacheNode<K, V> next;
        K key;
        V value;
        CacheDeque<K, V> owner;

        CacheNode() {}

        CacheNode(final K key, final V value) {
            this.key = key;
            this.value = value;
        }

        /**
         * 移除指定元素
         */
        public static <K, V> CacheNode<K, V> withdrawNode(final CacheNode<K, V> node) {
            if (node != null && node.prev != null) {
                node.prev.next = node.next;
                if (node.next != null) {
                    node.next.prev = node.prev;
                }
            }
            return node;
        }
    }

    /**
     * 左边last，右边first。即左右双dummy node
     */
    private static class CacheDeque<K, V> {

        CacheNode<K, V> last;
        CacheNode<K, V> first;
        CacheDeque<K, V> nextDeque;

        /**
         * Constructs list and initializes last and first pointers.
         */
        CacheDeque() {
            last = new CacheNode<>();
            first = new CacheNode<>();
            last.next = first;
            first.prev = last;
        }

        /**
         * 添加到last后
         */
        CacheNode<K, V> addLast(final K key, final V value) {
            CacheNode<K, V> node = new CacheNode<>(key, value);
            node.owner = this;
            node.next = last.next;
            node.prev = last;
            node.next.prev = node;
            last.next = node;
            return node;
        }

        /**
         * 添加到last后
         */
        CacheNode<K, V> addLastNode(final CacheNode<K, V> node) {
            node.owner = this;
            node.next = last.next;
            node.prev = last;
            node.next.prev = node;
            last.next = node;
            return node;
        }

        /**
         * 取出第一个node（next、prev设为null）
         */
        CacheNode<K, V> pollFirst() {
            CacheNode<K, V> node = null;
            if (first.prev != last) {
                node = first.prev;
                first.prev = node.prev;
                first.prev.next = first;
                node.prev = null;
                node.next = null;
            }
            return node;
        }

        /**
         * 是否为空校验，左右双dummy node
         */
        boolean isEmpty() {
            return last.next == first;
        }
    }
}
